package common.sort;

/**
 * 原理:
 * 用数组记录原数出现的次数 (试用于数值相近)
 */
public class CountingSort implements Sort {

    @Override
    public void sort(int[] array) {
        int min = array[0];
        int max = array[0];

        // 找出最大值与最小值
        for (int i = 1; i < array.length; i++) {
            if (min > array[i]) {
                min = array[i];
            }
            if (max < array[i]) {
                max = array[i];
            }
        }

        int diff = max - min;
        if (diff == 0) {
            return;
        }

        int[] arrayResult = new int[max - min + 1];
        for (int i = 0; i < array.length; i++) {
            arrayResult[array[i] - min]++;
        }

        int idx = 0;
        for (int i = 0; i < arrayResult.length; i++) {
            for (int j = 0; j < arrayResult[i]; j++) {
                array[idx++] = min + i;
            }
        }
    }
}
